package DP.路径;

import MyUtils.MHUtils;
import org.junit.Test;

/**
 * 绑
 *      i <= N-1
 *      j <= M-2 [右侧一旦定 大概率不变]
 */
public class 第一行下到最后一行_最小路径_931 {
    public int min3(int a, int b, int c){
        int min1 = Math.min(a, b);
        int min2 = Math.min(c,min1);
        return min2;
    }
    public int minFallingPathSum(int[][] g) {
        int N = g.length;
        int M = g[0].length + 2;
        int[][] dp = new int[N][M];

        // 两边9
        for (int i = 0; i < N - 1; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][M-1] = Integer.MAX_VALUE;
        }
        // 第一行
        for (int j = 1; j <= M-2; j++) {
            dp[0][j] = g[0][j-1];
        }

        for (int i = 1; i <= N-1; i++) {
            for (int j = 1; j <= M-2; j++) {
                dp[i][j] = g[i][j-1] + min3(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]);
            }
        }

        // 遍历 最后一行 -> min
        int minRes = Integer.MAX_VALUE;
        for (int j = 1; j <= M-2; j++) {
            if(dp[N-1][j] < minRes){
                minRes = dp[N-1][j];
            }
        }
        return minRes;
    }

    @Test
    public void test() {
        int[][] g = {{2,1,3},{6,5,4},{7,8,9}};
        MHUtils.ptIntShuzu(g);
        System.out.println("RES: " + minFallingPathSum(g));
    }
}
